package main.Q401_500;

import java.util.*;

public class Q441_450 {
    public static void main(String[] args) {
        System.out.println("Question441：排列硬币");
        System.out.println("Question442：数组中重复的数据");
        int[] arr={1};
        System.out.println(Question442.findDuplicates(arr));
        System.out.println("Question443：");
        System.out.println("Question444：");
        System.out.println("Question445：两数相加Ⅱ");
        System.out.println("Question446：");
        System.out.println("Question447：");
        System.out.println("Question448：找到所有数组中消失的数字");
        System.out.println("Question449：序列化和反序列化二叉搜索树");
        System.out.println("Question450：删除二叉搜索树中的节点");
    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Question441{
    public static int arrangeCoins(int n) {
        return (int) ((Math.sqrt((long) 8 * n + 1) - 1) / 2);
    }
}

class Question442{
    public static List<Integer> findDuplicates(int[] nums) {
        List<Integer> list=new ArrayList<>();
        for (int i=0;i< nums.length;){
            int temp=nums[i];
            while (i!=nums[i]-1&&temp!=nums[temp-1]){
                int swapNum=nums[temp-1];
                nums[temp-1]=nums[i];
                nums[i]=swapNum;
                temp=swapNum;
            }
            i++;
        }
        for (int i=0;i< nums.length;i++){
            if (i!=nums[i]-1) list.add(nums[i]);
        }
        return list;
    }
}

class Question445{
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Deque<Integer> stack1 = new ArrayDeque<Integer>();
        Deque<Integer> stack2 = new ArrayDeque<Integer>();
        while (l1 != null) {
            stack1.push(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            stack2.push(l2.val);
            l2 = l2.next;
        }
        int carry = 0;
        ListNode result = null;
        while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) {
            int a = stack1.isEmpty() ? 0 : stack1.pop();
            int b = stack2.isEmpty() ? 0 : stack2.pop();
            int cur = a + b + carry;
            carry = cur / 10;
            cur %= 10;
            ListNode curnode = new ListNode(cur);
            curnode.next = result;
            result = curnode;
        }
        return result;
    }
}

class Question448{
    public List<Integer> findDisappearedNumbers(int[] nums) {
        /*
        * 由于元素在1-n范围内，且数组长度为n则，存在的元素可与角标相对应。
        * */
        List<Integer> list=new ArrayList<>();
        for (int num:nums) nums[((num-1)%nums.length)]+= nums.length;//将元素所对应的角标元素改变至范围以外
        for (int i=0;i< nums.length;i++)//找到在范围以内元素的角标，该角标即对应了未存在的元素
            if (nums[i]<= nums.length) list.add(i+1);
        return list;
    }
}

class Question449{
    public String serialize(TreeNode root) {
        StringBuffer stringBuffer=new StringBuffer();
        if (root!=null){
            Stack<TreeNode> stack=new Stack<>();
            stack.add(root);
            while (!stack.isEmpty()){
                TreeNode curNode=stack.pop();
                stringBuffer.append(curNode.val);
                if (curNode.left!=null) stack.push(curNode.left);
                if (curNode.right!=null) stack.push(curNode.right);
            }
        }
        return stringBuffer.toString();
    }

    public TreeNode deserialize(String data) {
        return null;
    }
}

class Question450{
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) {
            return null;
        }
        if (root.val > key) {
            root.left = deleteNode(root.left, key);
            return root;
        }
        if (root.val < key) {
            root.right = deleteNode(root.right, key);
            return root;
        }
        if (root.val == key) {
            if (root.left == null && root.right == null) {
                return null;
            }
            if (root.right == null) {
                return root.left;
            }
            if (root.left == null) {
                return root.right;
            }
            TreeNode successor = root.right;
            while (successor.left != null) {
                successor = successor.left;
            }
            root.right = deleteNode(root.right, successor.val);
            successor.right = root.right;
            successor.left = root.left;
            return successor;
        }
        return root;
    }
}